//
// Created by Administrator on 2022/1/3.
//

#ifndef CPP_LEARNING_SPLAY_TREE_HPP
#define CPP_LEARNING_SPLAY_TREE_HPP


#include "BST.hpp"
template <typename T>
class SplayTree: public BST<T>{

protected:
    BinNodePosi(T) splay(BinNodePosi(T) node);
    void rightRotate(BinNodePosi(T) p);
    void leftRotate(BinNodePosi(T) p);


public:
    /**
     * 查找成功， 将要查找的的node 提升至 树根
     * 查找失败, 将最后一个被访问的节点提升至树根
     * @param e
     * @return
     */
    BinNodePosi(T)  search(const T&e);   // 查找
    BinNodePosi(T) insert(const T& e);    // 插入
    bool remove(const T&e);           // 删除
};
template <typename T>
BinNodePosi(T) SplayTree<T>::insert(const T& e){
    BinNodePosi(T) node = BST<T>::insert(e);
    return splay(node);
}
template <typename T>
bool SplayTree<T>::remove(const T&e){
    this->_hot = NULL;
    bool isDeleteSucc = BST<T>::remove(e);
    splay(this->_hot);
    return isDeleteSucc;
}


template <typename T>
BinNodePosi(T)  SplayTree<T>::search(const T&e){
    BinNodePosi(T) node = BST<T>::search(e);
    splay(node?node:this->_hot);
    return node;
}

/**
 * 以p进行右旋
 *                 g
 *        p
 *    v
 *
 *
 *               g
 *        v
 *             p
 */
template <typename T>
void SplayTree<T>::rightRotate(BinNodePosi(T) p){
    BinNodePosi(T) g = p->parent;
    BinNodePosi(T) v = p->lc;
    BinNodePosi(T) vrc = v->rc;
    BinNodePosi(T)& fromParentReference = FromParentTo(*p);

    v->parent = g;
    fromParentReference = v;

    v->rc = p;
    p->parent = v;

    p->lc = vrc;
    if(vrc) vrc->parent = p;

}


/**
 * 以p进行左旋
 *   g
 *        p
 *              v
 *
 *
 *     g
 *            v
 *        p
 */

template <typename T>
void SplayTree<T>::leftRotate(BinNodePosi(T) p){

    BinNodePosi(T) g = p->parent;
    BinNodePosi(T) v = p->rc;
    BinNodePosi(T) vlc = v->lc;
    BinNodePosi(T)& fromParentReference = FromParentTo(*p);

    v->parent = g;
    fromParentReference = v;

    v->lc = p;
    p->parent = v;

    p->rc = vlc;
    if(vlc) vlc->parent = p;

}



/**
 *                 g
 *        p
 *
 *  v
 */
template <typename T>
BinNodePosi(T) SplayTree<T>::splay(BinNodePosi(T) node){
    // 两层伸展
    while((node !=NULL) && (node ->parent != NULL)) {

        BinNodePosi(T)p = NULL;
        BinNodePosi(T)g = NULL;

        p = node->parent;
        if (p) g = p->parent;

        // 双层伸展的奇数情况
        if (g == NULL) {
            if (IsLChild(*node)) {
                rightRotate(p);
            } else if (IsRChild(*node)) {
                leftRotate(p);
            }

        }else{
            /**
             *                g
             *       p
             *  v
             */
            // 双层伸展的双数情况  LL
            if(IsLChild(*node) && IsLChild(*p)){
                rightRotate(g);
                rightRotate(p);
            }

            /**
             *            g
             *      p
             *          v
             */
            // LR
            else if(IsRChild(*node) && IsLChild(*p)){
                leftRotate(p);
                rightRotate(g);
            }

            /**
             *            g
             *               p
             *                   v
             */
            // RR
            else if(IsRChild(*node) && IsRChild(*p)){
                leftRotate(g);
                leftRotate(p);
            }

            /**
             *            g
             *                  p
             *               v
             */
            // RL
            else if(IsLChild(*node) && IsRChild(*p)){
                rightRotate(p);
                leftRotate(g);
            }
        }

    }

    return node;
}

#endif //CPP_LEARNING_SPLAY_TREE_HPP
